package com.ly.tree;

import org.w3c.dom.ls.LSOutput;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree<T extends Comparable<T>> {
    public com.ly.tree.Node root;
    BinaryTree(){
        root = null;
    }


    public void print(){
        //打印二叉树 （层序遍历）
        Queue<com.ly.tree.Node> queue = new LinkedList<com.ly.tree.Node>();

        queue.offer(root);
        while (!queue.isEmpty()){
            com.ly.tree.Node temp = queue.poll();
            System.out.print(temp.value+" ");
            if (temp.left != null){
                queue.offer(temp.left);
            }
            if (temp.right != null){
                queue.offer(temp.right);
            }
        }
    }
    public void preOrder(){
                   //先序
        Stack<com.ly.tree.Node> stack = new Stack<com.ly.tree.Node>();
        stack.push(root);
        while (!stack.isEmpty()){
            com.ly.tree.Node temp = stack.pop();
            System.out.print(temp.value + " ");
            if (temp.right != null){
                stack.push(temp.right);
            }
            if (temp.left != null){
                stack.push(temp.left);
            }
        }
    }
    public void inOrder(){
              //中序
        Stack<com.ly.tree.Node> stack = new Stack<com.ly.tree.Node>();
        com.ly.tree.Node<T> temp = root;
        while (!stack.isEmpty() || temp != null){
            if (temp != null){
                stack.push(temp);
                temp = temp.left;
            }else {
                temp = stack.pop();
                System.out.print(temp.value + " ");
                temp = temp.right;
            }
        }
    }

    public  void postOrder() {
                  //后序
        com.ly.tree.Node<T> temp = root;
        if(temp != null) {
            Stack<com.ly.tree.Node> stack1 = new Stack<>();
            Stack<com.ly.tree.Node> stack2 = new Stack<>();
            stack1.push(temp);
            while(!stack1.isEmpty()) {
                temp = stack1.pop();
                stack2.push(temp);
                if(temp.left != null)
                    stack1.push(temp.left);
                if(temp.right != null)
                    stack1.push(temp.right);
            }
            while(!stack2.isEmpty())
                System.out.print(stack2.pop().value + " ");
        }
    }



    public void insert(T val){
                   //增加
        com.ly.tree.Node<T> newNode = new com.ly.tree.Node<T>(val);
        com.ly.tree.Node<T> temp = root;
        com.ly.tree.Node<T> current = root;

        if (temp == null){
            root = newNode;
        }else {
            while (temp != null){
                if (val.compareTo(temp.value) == 0){
                    break;
                }else if (val.compareTo(temp.value) < 0){
                    if (temp.left != null) {
                        temp = temp.left;
                    }else {
                        temp.left = newNode;
                        break;
                    }
                }else{
                    if (temp.right != null){
                        temp = temp.right;
                    }else{
                        temp.right = newNode;
                        break;
                    }
                }
            }
        }
    }
    public boolean search(T val){
        if (root == null){
            return false;
        }
        com.ly.tree.Node<T> temp = root;
        while (temp != null){
            if (val.compareTo(temp.value) == 0){
                return true;
            }else if (val.compareTo(temp.value) < 0){
                temp = temp.left;
            }else {
                temp = temp.right;
            }
        }
        return false;
    }

    public void delete(T val){
        com.ly.tree.Node<T> current = root;
        com.ly.tree.Node<T> parent = root;
        if (root == null){
            return;
        }

        while (current != null){
            if (val.compareTo(current.value) == 0){
                break;
            }else if (val.compareTo(current.value) < 0){
                parent = current;
                current = current.left;
            }else {
                parent = current;
                current = current.right;
            }
        }
                  //定位
        if (current != null){
            if (current.left == null && current.right == null){
                if (current == root){
                    root = null;
                }else if (parent.left == current){
                    parent.left = null;
                }else {
                    parent.right = null;
                }
            }else if (current.left == null || current.right == null){
                //只有左右单独一个子树
                if (current == root){
                    if (current.left != null){
                        root=current.left;
                    }else {
                        root=current.right;
                    }
                }else if (parent.left == current){
                    if (current.left != null){
                        parent.left = current.left;
                    }else {
                        parent.left = current.right;
                    }
                }else {
                    if (current.left != null){
                        parent.right = current.left;
                    }else {
                        parent.right = current.right;
                    }
                }
            }else {


                com.ly.tree.Node<T> leftNode = current.left;
                T leftMax = foundLeftMaxRightAndDelete(leftNode);
                current.value = leftMax;

            }
        }
    }
    private T foundLeftMaxRightAndDelete(com.ly.tree.Node<T> root){
        com.ly.tree.Node<T> temp = root;
        com.ly.tree.Node<T> parent = root;
        while (temp != null && temp.right != null){
            parent = temp;
            temp = temp.right;
            if (temp.left != null){
                temp = temp.left;
                if (temp.right == null){
                    temp = parent;
                    temp = temp.right;
                }
            }
        }
        if (temp != null){
            parent.right = null;
            return temp.value;
        }else {
            return null;
        }
    }
}